/*
 *https://leetcode.cn/problems/find-if-path-exists-in-graph/description/
 *1971. 寻找图中是否存在路径
 *easy 叶佳豪 2024.10.25
*/

class Solution {
private:
    vector<int> father;

    // 初始化并查集
    void init(int n){
        father = vector<int>(n, 0);
        for(int i = 0; i < n; i++) father[i] = i;
    }

    // 并查集寻根过程
    int find(int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    // 判断 u 和 v 是否找到同一个跟
    bool isSame(int u, int v){
        return find(u) == find(v);
    }

    // 将v->u 这条边加入并查集
    void join(int u, int v){
        u = find(u); // 寻找 u 的根
        v = find(v); // 寻找 v 的根
        if(u == v) return;
        father[u] = v;
    }

public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if(source == destination) return true;
        init(n);
        for(int i = 0; i < edges.size(); i++){
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source, destination);
    }
};